#include <iostream>
#include <vector>

void adjust_down(std::vector<int>& list, int idx, int len)
{
    for(int i = idx; i < len;)
    {
        if(i*2<len && i*2+1<len)
        {
            if(list[i] < list[i*2])
            {
                if(list[i*2] < list[i*2+1])
                {
                    std::swap(list[i], list[i*2+1]);
                    i = i*2+1;
                }
                else
                {
                    std::swap(list[i], list[i*2]);
                    i = i*2;
                }
            }
            else if(list[i] < list[i*2+1])
            {
                std::swap(list[i], list[i*2+1]);
                i = i*2+1;
            }
            else
                break;
        }
        else if(i*2<len && i*2+1>=len)
        {
            if(list[i] < list[i*2])
            {
                std::swap(list[i], list[i*2]);
                i = i*2;
            }
            else
                break;
        }
        else
            i = i*2;
    }
}

void build_heap(std::vector<int>& list)
{
    for(int i = (list.size()-1)/2; i > 0; i--)
    {
        adjust_down(list, i, list.size());
    }
}

void heap_sort(std::vector<int>& list)
{
    build_heap(list);
    for(int i = list.size()-1; i > 0; i--)
    {
        std::swap(list[i], list[1]);
        adjust_down(list, 1, i);
    }
}

int main()
{
    std::vector<std::vector<int>> list = {
        {},
        {1},
        {1,2},
        {2,1},
        {1,2,3,4},
        {4,3,2,1},
        {4,2,3,1},
        {4,3,1,2,5},
        {4,1,2,5,7,10,5,6,1,2,3,11,9,8,3}
    };

    for(int i = 0; i < list.size(); i++)
    {
        for(auto v : list[i])
            std::cout << v << " ";
        
        heap_sort(list[i]);

        std::cout << " --> ";
        for(auto v : list[i])
            std::cout << v << " ";
        std::cout << std::endl;
    }

    return 0;
}